Sorting networks are useful as fast circuits for performing data sorting. Sorting networks consist of input terminals, a plurality of comparison circuits, interconnections or links and output terminals. A comparison circuit is operable to compare two values appearing at its inputs and to route them to respective outputs based on those values. For example, the lesser of the two values may be directed to a predetermined first output and the greater of the two values may be directed to a predetermined second output of the comparison circuit. Sorting networks are useable, for example, in conjunction with parallel processing for computers, and as message routers for sorting messages such as in data and telecommunication networks.
It is desirable to implement sorting networks into an ever-decreasing area within an electrical circuit. Decreasing the comparison circuit count may help in minimizing sorting network layout area. The earliest sorting networks required (N).sup.2 /2 comparison circuits, where N is the number of signals to be sorted and routed. That requirement was significantly decreased in a bitonic sorting network attributed to K. Batcher requiring O(N log.sup.2 N) comparison circuits. See, K. Batcher, "Sorting Networks and their Applications," Proc. AFIPS Spring Joint Computing Conf., vol. 32, pp. 307-314, 1968. A later variation of Batcher's bitonic network, reported by D. E. Knuth, is described later in this specification. See, Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Section 5.3.4, (Addison-Wesley , 1973).
The area required for a sorting network is not, however, necessarily controlled by the number of comparison circuits in the network. An additional important consideration is the area required for the interconnects, e.g., wires or the like, linking the various elements of the sorting network. As such, the physical layout of a sorting network may be of paramount importance in minimizing area requirements.